package Lee_code;

import java.text.BreakIterator;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author blh
 * @date 2024年07月30日 9:43
 */
public class Lee_210_730 {
    List<List<Integer>> edges;
    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    int[] visited;
    int[] result;
    // 判断是否有环
    boolean valid = true;
    // 栈下标
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        // 初始化List
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        result = new int[numCourses];
        index = numCourses - 1;
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }

        if (!valid) {
            return new int[0];
        }
        return result;
    }

    private void dfs(int u) {
        // 将节点标记为搜索中
        visited[u] = 1;
        // 搜索其相邻节点
        // 如果有环,立即停止搜索
        for (int v: edges.get(u)){
            // 如果未搜索, 搜索相邻节点
            if (visited[v]==0){
                dfs(v);
                if (!valid){
                    return;
                } else if (visited[v]==1) {
                    // 发现有环
                    valid=false;
                    return;
                }
                visited[u] = 2;
                result[index--] = u;
            }
        }
    }

}
